#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>

struct HuffmanNode {
    char data;
    unsigned freq;
    HuffmanNode *left, *right;

    HuffmanNode(char data, unsigned freq) : data(data), freq(freq), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(HuffmanNode* l, HuffmanNode* r) {
        return l->freq > r->freq;
    }
};

void generateCodes(HuffmanNode* root, std::string str, std::unordered_map<char, std::string> &huffmanCode) {
    if (!root)
        return;
    if (!root->left && !root->right) {
        huffmanCode[root->data] = str;
    }
    generateCodes(root->left, str + "0", huffmanCode);
    generateCodes(root->right, str + "1", huffmanCode);
}

int main() {
    std::vector<HuffmanNode*> nodes = {
       new HuffmanNode('a', 5), new HuffmanNode('b', 29), new HuffmanNode('c', 7),
       new HuffmanNode('d', 8), new HuffmanNode('e', 14), new HuffmanNode('f', 23),
       new HuffmanNode('g', 3), new HuffmanNode('h', 11)
    };

    std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, Compare> pq;
    for (auto node : nodes) {
        pq.push(node);
    }

    while (pq.size() > 1) {
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop();

        HuffmanNode* sum = new HuffmanNode('\0', left->freq + right->freq);
        sum->left = left;
        sum->right = right;
        pq.push(sum);
    }

    std::unordered_map<char, std::string> huffmanCode;
    generateCodes(pq.top(), "", huffmanCode);

    for (auto pair : huffmanCode) {
        std::cout << pair.first << ": " << pair.second << " (" << pair.second.length() << " bits)" << std::endl;
    }

    return 0;
}
